public class Solution935 {
    public int knightDialer(int n) {
        int m=1000000007;
        int[] f=new int[10];
        for (int i=0;i<=9;i++){
            f[i]=1;
        }
        for (int i=2;i<=n;i++){
            int[] g=new int[10];
            g[0]=(f[4]+f[6])%m;
            g[1]=(f[6]+f[8])%m;
            g[2]=(f[7]+f[9])%m;
            g[3]=(f[4]+f[8])%m;
            g[4]=((f[3]+f[9])%m+f[0])%m;
            g[6]=((f[1]+f[7])%m+f[0])%m;
            g[7]=(f[2]+f[6])%m;
            g[8]=(f[1]+f[3])%m;
            g[9]=(f[2]+f[4])%m;
            f=g;
        }
        int ans=0;
        for (int i=0;i<=9;i++){
            ans=(ans+f[i])%m;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution935().knightDialer(3131));
    }
}
